#ifndef _CIRCLE_DIAGRAM_H_
#define _CIRCLE_DIAGRAM_H_

#include <vector>
#include <algorithm>
#include <set>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Regular_triangulation_vertex_base_2.h>
#include <CGAL/Regular_triangulation_face_base_2.h>
#include <CGAL/Regular_triangulation_euclidean_traits_2.h>
#include <CGAL/Regular_triangulation_2.h>

#include "circle_union.h"

namespace Packing_common
{
	// temporarily use power diagram as the diagram among the circles
	template < class Gt, class Vb = CGAL::Regular_triangulation_vertex_base_2<Gt> >
	class Vertex_2 : public Vb
	{
	public:
		typedef typename Vb::Vertex_handle Vertex_handle;
		typedef typename Vb::Face_handle	Face_handle;
		//typedef typename Vb::Point			Point;
		typedef typename Vb::Weighted_point	Weighted_point;

		template < typename TDS2 >
		struct Rebind_TDS
		{
			typedef typename Vb::template Rebind_TDS<TDS2>::Other Vb2;
			typedef Vertex_2<Gt, Vb2> Other;
		};
	public:
		Vertex_2() : Vb() { }
		Vertex_2(const Weighted_point& wp) : Vb(wp) { };
		Vertex_2(const Weighted_point& wp, Face_handle f) : Vb(wp, f) { }

	public:
		unsigned int group_id;
	};

	template < class Gt, class Fb = CGAL::Regular_triangulation_face_base_2<Gt> >
	class Face_2 : public Fb
	{
	public:
		typedef typename Fb::Vertex_handle	Vertex_handle;
		typedef typename Fb::Face_handle	Face_handle;

		template < typename TDS2 >
		struct Rebind_TDS
		{
			typedef typename Fb::template Rebind_TDS<TDS2>::Other Fb2;
			typedef Face_2<Gt, Fb2>	Other;
		};
	public:
		Face_2() : Fb() { }
		Face_2(Vertex_handle v0, Vertex_handle v1, Vertex_handle v2) : Fb(v0, v1, v2) {}
		Face_2(Vertex_handle v0, Vertex_handle v1, Vertex_handle v2,
				Face_handle n0, Face_handle n1, Face_handle n2) : Fb(v0,v1,v2,n0,n1,n2) {}
	};

	typedef CGAL::Regular_triangulation_euclidean_traits_2< CGAL::Exact_predicates_inexact_constructions_kernel >	Traits;
	typedef CGAL::Triangulation_data_structure_2< Vertex_2<Traits>, Face_2<Traits> > TDS;

	class Circle_diagram : public CGAL::Regular_triangulation_2<Traits, TDS> 
	{
		typedef CGAL::Regular_triangulation_2<Traits, TDS> baseclass;
		typedef baseclass::Weighted_point Weighted_point;

	public:
		void insert(const std::vector<Circle_union>& circle_unions);
		
		void clear();

		void neighbor_pairs(std::vector< std::pair<unsigned int, unsigned int> >& proximal_pairs);

	private:
		std::vector< std::vector<Vertex_handle> > vgroups; // grouped vertices according to the group IDs
	};
}
#endif